// https://leetcode.cn/problems/distinct-subsequences/description/

// 算法思路总结：
// 1. 使用动态规划计算s的子序列中t出现的次数
// 2. dp[i][j]表示t前i个字符在s前j个字符中出现的次数
// 3. 初始化：空字符串是任何字符串的子序列
// 4. 字符匹配时累加两种情况：使用当前字符匹配 + 跳过当前字符
// 5. 时间复杂度：O(n×m)，空间复杂度：O(n×m)

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <algorithm> 

class Solution 
{
public:
    typedef unsigned long long ull;
    int numDistinct(string s, string t) 
    {
        int m = s.size(), n = t.size();

        vector<vector<ull>> dp(n + 1, vector<ull>(m + 1, 0));
        for (int j = 0 ; j <= m ; j++)
            dp[0][j] = 1;

        s = " " + s, t = " " + t;
        for (int i = 1 ; i <= n ; i++)
        {
            for (int j = i ; j <= m ; j++)
            {
                dp[i][j] = dp[i][j - 1];
                if (s[j] == t[i])
                    dp[i][j] += dp[i - 1][j - 1];
            }
        }

        return dp[n][m];
    }
};

int main()
{
    string s11 = "rabbbit", s12 = "rabbit";
    string s21 = "babgbag", s22 = "bag";

    Solution sol;

    cout << sol.numDistinct(s11, s12) << endl;
    cout << sol.numDistinct(s21, s22) << endl;

    return 0;
}